[리트코드] 5.Longest Palindromic Substring
💯 solving-algo | February 12, 2021
문제 주소
가장 긴 팰린드롬을 찾는 문제이며, 여러 개의 입력 중 가장 긴 길이를 찾는 것은 다이나믹 프로그래밍이 일반적이지만 투포인터를 활용 https://leetcode.com/problems/longest-palindromic-substring/
My Solution
class Solution:
def longestPalindrome(self, s: str) -> str:
# 판별 대상이 아닌 것은 빠르게 return
if len(s) < 2 or s == s[::-1]:
return s
# 투 포인터를 이용해 확장
def expand(left, right):
while left >= 0 and right <= len(s) and s[left] == s[right - 1]:
left -= 1
right += 1
return s[left + 1 : right - 1]
# 홀수와 짝수로 팰린드롬을 모두 판별
result = ''
for i in range(len(s) - 1):
result = max(result,
expand(i, i + 1),
expand(i, i + 2),
key=len)
return result풀이 방법
투 포인터와 슬라이딩 윈도우를 활용했다. expand 함수를 통해 팰린드 롬 조건에 부합하는 중간 값을 찾으면 left, right로 범위를 확장하여 가장 긴 값을 출력하는 형식이다.
또한 max 함수는 팰린드 롬의 특성상 홀수/짝수를 모두 판별해 봐야 하기 때문에 그 중에서 가장 긴 값을 키 값으로 len 함수를 이용하였다.
